package cn.ycc1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的遍历
 * @author ycc
 * @date 2024/6/5
 */
public class BinaryTreeTraversal {
    public static void main(String[] args) {
        // 构建一个二叉树
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);
        root.right.right.left = new Node(8);

        // 前序遍历
        System.out.println("前序遍历：");
        preorderTraversal(root);
        System.out.println();

        // 中序遍历
        System.out.println("中序遍历：");
        inorderTraversal(root);
        System.out.println();

        // 后序遍历
        System.out.println("后序遍历：");
        postorderTraversal(root);
        System.out.println();

        // 层序遍历
        System.out.println("层序遍历：");
        levelTraversal(root);
        System.out.println();

        printTreeShape(root, 0);
        printLevelOrder(root);
//        levelOrderPrint(root);
    }


    public static void levelOrderPrint(Node root) {
        if (root == null) {
            return;
        }

        Queue<Node> queue = new LinkedList<>();
        Queue<Character> queueDirection = new LinkedList<>(); // 用于存储左右子节点的方向
        queue.offer(root);
        queueDirection.offer('L'); // 假设根节点为'L'方向

        while (!queue.isEmpty()) {
            int size = queue.size(); // 当前层的节点数
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                char direction = queueDirection.poll();
                System.out.print(direction == 'L' ? "L" : "R"); // 打印左右标识
                System.out.print(node.value + " ");
                if (node.left != null) {
                    queue.offer(node.left);
                    queueDirection.offer('L');
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    queueDirection.offer('R');
                }
            }
            System.out.println(); // 换行打印下一层
        }
    }

    /**
     * 打印二叉树
     * 先把二叉树的结构记录下来，然后打印出来
     * @param root
     * 1. 记录每一层的节点数
     * 2. 记录每个节点是否有左右子节点
     * 3. 记录层数，从1开始
     * 4. 记录最大层的节点数
     */
   public static void printLevelOrder(Node root) {
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int nodeCount = queue.size();
            while (nodeCount > 0) {
                Node node = queue.poll();
                System.out.print(node.value + " ");
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
                nodeCount--;
            }
            System.out.println();
        }

       // 示例树:
       //      1
       //     / \
       //    2   3
       //   / \  / \
       //  4   5 6  7
       //          /
       //         8

       int level = 4;
       int maxNodes = 4;
       List<List<Integer>> list = new ArrayList<>();
       List<Integer> levelNodes1 = new ArrayList<>();
       levelNodes1.add(1);
       list.add(levelNodes1);

       List<Integer> levelNodes2 = new ArrayList<>();
       levelNodes2.add(2);
       levelNodes2.add(3);
       list.add(levelNodes2);

       List<Integer> levelNodes3 = new ArrayList<>();
       levelNodes3.add(4);
       levelNodes3.add(5);
       levelNodes3.add(6);
       levelNodes3.add(7);
       list.add(levelNodes3);

       List<Integer> levelNodes4 = new ArrayList<>();
       levelNodes4.add(0);
       levelNodes4.add(0);
       levelNodes4.add(0);
       levelNodes4.add(0);
       levelNodes4.add(0);
       levelNodes4.add(0);
       levelNodes4.add(8);
       levelNodes4.add(0);
       list.add(levelNodes4);

        for (int i = 0; i < level; i++) {
            List<Integer> temp = list.get(i);
//            int spaces = maxNodes / 2 - temp.size() / 2;
//            int spaces = maxNodes / temp.size() - 1;
//            int spaces = maxNodes / temp.size() * level - 1;
//            int spaces = maxNodes / temp.size() * (i+1) - 1;
            int spaces = maxNodes / temp.size() * 2 - 1;
            for (int j = 0; j < temp.size(); j++) {
                for (int k = 0; k < spaces; k++) {
                    System.out.print(" ");
                }
                if(temp.get(j) == 0){
                    System.out.print(" ");
                }else{
                    System.out.print(temp.get(j));
                }
//                System.out.print(temp.get(j));
            }
            System.out.println();
        }
    }

    /**
     * 打印二叉树形状
     * @param node
     * @param space
     * 先输出右子树，再输出左子树，最后输出根节点
     */
    public static void printTreeShape(Node node, int space) {
        if (node == null) {
            return;
        }

        // 增加空格，使输出更美观
        space += 8;

        printTreeShape(node.right, space);

//        System.out.println();
        for (int i = 8; i < space; i++) {
            System.out.print(" ");
        }
        System.out.println(node.value);

        printTreeShape(node.left, space);
    }

    // 前序遍历
    public static void preorderTraversal(Node node) {
        if (node == null) return;
        System.out.print(node.value + " "); // 输出根节点 node为当前节点可理解为根节点或相应子树的根节点
        preorderTraversal(node.left);
        preorderTraversal(node.right);
    }

    // 中序遍历
    public static void inorderTraversal(Node node) {
        if (node == null) return;
        inorderTraversal(node.left);
        System.out.print(node.value + " "); // node表示根节点（当前节点）
        inorderTraversal(node.right);
    }

    // 后序遍历
    public static void postorderTraversal(Node node) {
        if (node == null) return;
        postorderTraversal(node.left);
        postorderTraversal(node.right);
        System.out.print(node.value + " "); // 最后输出根节点是后序遍历
    }
    // 层序遍历
    public static void levelTraversal(Node node) {
        if (node == null) return;
        // 队列
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.value + " ");
            if (cur.left != null) queue.add(cur.left);
            if (cur.right != null) queue.add(cur.right);
        }
    }
}
